package com.caochenlei.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

//计算器主程序
public class Calculator {
    public static void main(String[] args) {
        String expression = "(1+((2+3)×4)-5)%10/0.5";

        //1.去除表达式所有空格
        expression = expression.replaceAll("\\s+", "");
        System.out.println("去除表达式所有空格：" + expression);

        //2.替换表达式乘法符号
        expression = expression.replaceAll("×", "*");
        System.out.println("替换表达式乘法符号：" + expression);

        //3.表达式转为中缀集合
        List<String> infixList = strToInfixList(expression);
        System.out.println("表达式转为中缀集合：" + infixList);

        //4.中缀转为后缀表达式
        List<String> suffixList = infixToSuffixList(infixList);
        System.out.println("中缀转为后缀表达式：" + suffixList);

        //5.开始计算后缀表达式
        double result = calculate(suffixList);
        System.out.println("开始计算后缀表达式：" + result);
    }

    private static List<String> strToInfixList(String expression) {
        //1.创建集合
        List<String> list = new ArrayList<>();
        //2.定义指针
        int i = 0;
        //3.获取字符
        char c;
        //4.循环遍历
        do {
            //如果此字符非数字，直接加入到集合中
            if ((c = expression.charAt(i)) < '0' || (c = expression.charAt(i)) > '9') {
                list.add(String.valueOf(c));
                i++;
            }
            //如果此字符是数字，还需要考虑多位数以及小数部分
            else {
                String str = "";
                while ((i < expression.length() && (c = expression.charAt(i)) >= '0' && (c = expression.charAt(i)) <= '9')
                        || (i < expression.length() && (c = expression.charAt(i)) == '.')) {
                    str += c;
                    i++;
                }
                list.add(str);
            }
        } while (i < expression.length());
        //5.返回集合
        return list;
    }

    private static List<String> infixToSuffixList(List<String> list) {
        //1.定义一个符号栈
        Stack<String> s1 = new Stack<>();
        //2.储存最后的结果
        List<String> s2 = new ArrayList<>();
        //3.循环遍历集合
        for (String item : list) {
            //如果是数字，直接入s2
            if (Operator.isNumber(item)) {
                s2.add(item);
            }
            //如果左括号，直接入s1
            else if (item.equals("(")) {
                s1.push(item);
            }
            //如果右括号，则依次弹出s1栈顶的运算符并压入s2，直到遇到左括号为止，此时将这一对括号消除
            else if (item.equals(")")) {
                while (s1.size() != 0 && !s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                s1.pop();//消除左括号
            }
            //当item的优先级小于等于s1栈顶运算符, 将s1栈顶的运算符弹出并加入到s2中，直到item的优先级大于s1栈顶运算符为止
            else {
                while (s1.size() != 0 && Operator.getPriority(item) <= Operator.getPriority(s1.peek())) {
                    s2.add(s1.pop());
                }
                s1.push(item);//item入s1
            }
        }
        //4.处理剩余运算符
        while (s1.size() != 0) {
            s2.add(s1.pop());
        }
        //5.返回最终的结果
        return s2;
    }

    private static double calculate(List<String> list) {
        //1.创建一个堆栈
        Stack<String> stack = new Stack<>();
        //2.循环遍历集合
        for (String item : list) {
            //如果是数字，该数字入栈
            if (Operator.isNumber(item)) {
                stack.push(item);
            }
            //如果非数字，计算后入栈
            else {
                double num2 = Double.parseDouble(stack.pop());
                double num1 = Double.parseDouble(stack.pop());
                double res = 0;
                if (item.equals("+")) {
                    res = num1 + num2;
                } else if (item.equals("-")) {
                    res = num1 - num2;
                } else if (item.equals("*")) {
                    res = num1 * num2;
                } else if (item.equals("/")) {
                    res = num1 / num2;
                } else if (item.equals("%")) {
                    res = num1 % num2;
                }
                stack.push(String.valueOf(res));
            }
        }
        //3.返回运算结果
        return Double.parseDouble(stack.pop());
    }
}

//计算器运算符
class Operator {
    private static int ADD_PRIORITY = 1;//代表加法运算符优先级
    private static int SUB_PRIORITY = 1;//代表减法运算符优先级
    private static int MUL_PRIORITY = 2;//代表乘法运算符优先级
    private static int DIV_PRIORITY = 2;//代表除法运算符优先级
    private static int SUR_PRIORITY = 2;//代表取余运算符优先级

    //判断是否是数字值
    public static boolean isNumber(String s) {
        return s.matches(("^(\\-|\\+)?\\d+(\\.\\d+)?$"));
    }

    //返回运算符优先级
    public static int getPriority(String operator) {
        int result = 0;
        switch (operator) {
            case "+": result = ADD_PRIORITY; break;
            case "-": result = SUB_PRIORITY; break;
            case "*": result = MUL_PRIORITY; break;
            case "/": result = DIV_PRIORITY; break;
            case "%": result = SUR_PRIORITY; break;
            default:  break;
        }
        return result;
    }
}
